/*!
 * \brief   Implémentation d'un graphe orienté où chaque sommet a un numéro et un nom
 * \author  Sébastien Caron - Alexandre Vaillancourt
 * \version 1.0
 * \date    Octobre 2011
 */

#include "Graphe.h"
#include <limits>
//vous pouvez inclure d'autres librairies si c'est nécessaire

using namespace std;

/**
* \brief Surcharge de l'opérateur de sortie.
* \fn std::ostream& operator<<(std::ostream& out, const Graphe& g)
*
* \param[in]	out		Le flux de sortie.
* \param[in]	g		Le graphe à afficher.
*
* \return	Le flux de sortie.
*/
ostream& operator<<( ostream& out, const Graphe& g)
{
	out << "Le graphe contient " << g.nbSommets << " sommet(s)" << std::endl;
	Graphe::Sommet* vertex = g.listSommets;
	while (vertex != NULL)
	{
		out << "Sommet no " << vertex->numero << ", nom : " << vertex->nom << std::endl;
		// Afficher les arcs.
		Graphe::Arc* arc = vertex->listeDest;
		if(arc!=NULL)
		{
			out << "Ce sommet a des liens vers le(s) sommet(s) : ";
			while (arc->suivDest != NULL)
			{
				out << arc->dest->numero << "(" << arc->cout << ")" << ",";
				arc = arc->suivDest;
			}
			out << arc->dest->numero << "(" << arc->cout << ")";
		}
		out << std::endl << std::endl;
		vertex = vertex->suivant;
	}
	return out;
}

/**
* \brief Surcharge de l'opérateur =
* \fn Graphe& operator = (const Graphe& source) throw (std::bad_alloc)
*
* \param[in]	source		Le graphe source a copier.
*
* \return	Copie du graphe source.
*/
Graphe& Graphe::operator=(const Graphe& source) throw (std::bad_alloc)
{
	this->_copierGraphe(source);
	return (*this);
}

//À compléter par les autres méthodes demandées sur le type Graphe

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Classes internes
// _________________________________________________________________________________________________

/**
* \brief Constructeur de Sommet
* \fn Graphe::Sommet::Sommet(int numero, const std::string & nom, int x, int y)
*
* \param[in]	numero	Le numéro de la station
* \param[in]	nom		Nom de la station
* \param[in]	x		Coordonnées x de la station
* \param[in]	y		Coordonnées y de la station
*/
Graphe::Sommet::Sommet(int numero, const std::string & nom, int x, int y){
	this->numero = numero;
	this->nom = nom;
	this->coord.x = x;
	this->coord.y = y;
	this->listeDest = 0;
	this->etat = false;
	this->predecesseur = 0;
	this->cout = 0;
	this->coutHeuristique = 0;
	this->precedent = 0;
	this->suivant = 0;
}

/**
* \brief Constructeur de Sommet
* \fn Graphe::Sommet::Sommet(Sommet* source)
*
* \param[in]	source	Le sommet source à copier
*/
Graphe::Sommet::Sommet(Sommet* source){
	// Ne copie pas les arcs
	this->numero = source->numero;
	this->nom = source->nom;
	this->coord.x = source->coord.x;
	this->coord.y = source->coord.y;
	this->listeDest = 0;
	this->etat = false;
	this->predecesseur = 0;
	this->cout = 0;
	this->coutHeuristique = 0;
	this->precedent = 0;
	this->suivant = 0;
}

/**
* \brief Destructeur de Sommet
* \fn Graphe::Sommet::~Sommet()
*
*/
Graphe::Sommet::~Sommet(){
	while(this->listeDest != 0){
		Arc* arcCourant = this->listeDest;
		this->listeDest = this->listeDest->suivDest;
		delete arcCourant;
	}
}

/**
* \brief Retourne le cout total d'un Sommet
* \fn int Graphe::Sommet::coutTotal()
*
*/
int Graphe::Sommet::coutTotal(){
	return this->cout + this->coutHeuristique;
}

/**
* \brief Constructeur avec paramètres
* \fn Arc(Sommet * dest, int cout)
*
* \param[in]	dest		Sommet de destination de l'arc.
* \param[in]    cout        Distance entre les deux sommets de l'arc.
*/
Graphe::Arc::Arc(Sommet * pDest, int pCout)
{
	dest = pDest;
	cout = pCout;
	suivDest = 0;
}

/**
* \brief Destructeur de l'arc
* \fn ~Arc()
*/
Graphe::Arc::~Arc()
{
	
}

/**
* \brief Constructeur avec paramètres
* \fn Graphe::Noeud::Noeud(Sommet* val)
*
* \param[in]	val		Le sommet source à mettre dans le Noeud
*/
Graphe::Noeud::Noeud(Sommet* val){
	this->precedent = 0;
	this->suivant = 0;
	this->val = val;
}

/**
* \brief Destructeur
* \fn Graphe::Noeud::~Noeud()
*
*/
Graphe::Noeud::~Noeud(){
	
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Constructeurs et destructeur
// _________________________________________________________________________________________________

/**
* \brief Constructeur par défaut du graphe
* \fn Graphe()()
*/
Graphe::Graphe()
{
	this->nbSommets = 0;
	this->listSommets = 0;
}

/**
* \brief Constructeur de copie
* \fn Graphe(const Graphe &source) throw (std::bad_alloc)
* \param[in]        source    Graphe source a copier
*/
Graphe::Graphe(const Graphe &source) throw (std::bad_alloc)
{
	this->nbSommets = 0;
	this->listSommets = 0;
	this->_copierGraphe(source);
}

/**
* \brief Destructeur du graphe
* \fn ~Graphe()
*/
Graphe::~Graphe(){
	this->_detruireGraphe();
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Ajout/suppression de sommets et d'arcs
// _________________________________________________________________________________________________

/**
* \brief Ajout d'un sommet au graphe
* \fn void Graphe::ajouterSommet(int numero, const std::string& nom, int x, int y) throw (std::bad_alloc, std::logic_error)
*
* \param[in]	numero	Le numéro de la station
* \param[in]	nom		Nom de la station
* \param[in]	x		Coordonnées x de la station
* \param[in]	y		Coordonnées y de la station
*/
void Graphe::ajouterSommet(int numero, const std::string& nom, int x, int y) throw (std::bad_alloc, std::logic_error){
	// Ajoute au début puisqu'il ne serait pas plus intéressant d'ajouter à la fin
	if (this->_getSommet(numero) != 0){
		throw std::logic_error("Un sommet avec ce numéro existe déjà");
	}
	Sommet* nouveau = new Sommet(numero, nom, x, y);
	nouveau->precedent = 0;
	nouveau->suivant = this->listSommets;
	if (this->listSommets != 0){
		this->listSommets->precedent = nouveau;
	}
	this->listSommets = nouveau;
	this->nbSommets++;
}

/**
* \brief	Enlève un sommet du graphe ainsi que tous les arcs qui vont et partent de ce sommet
* \fn void Graphe::enleverSommet(int numero) throw (std::logic_error)
*
* \param[in]	numero	Le numéro de la station à retirer
*/
void Graphe::enleverSommet(int numero) throw (std::logic_error){
	Sommet* aRetirer = this->_getSommet(numero);
	if (aRetirer == 0){
		throw std::logic_error("Un sommet avec ce numéro n'existe pas dans le graphe");
	}
	this->_enleverSommet(aRetirer);
}

/**
* \brief	Enlève tous les sommet du graphe qui ont le nom 'nom' ainsi que tous les arcs
*			qui venaient ou partaient de ces sommets
* \fn void Graphe::enleverSommets(const std::string& nom) throw (std::logic_error)
*
* \param[in]	nom		Le nom de la station à retirer
*/
void Graphe::enleverSommets(const std::string& nom) throw (std::logic_error){
	if (this->listSommets == 0){
		throw std::logic_error("Il n'y a aucun sommets dans le graphe");
	}
	Sommet* courant = this->listSommets;
	while (courant != 0){
		if (courant->nom == nom){
			Sommet* temp = courant;
			courant = courant->suivant;
			this->_enleverSommet(temp);
		}else{
			courant = courant->suivant;
		}
	}
}

/**
* \brief Ajout d'un arc au graphe
* \fn void ajouterArc(int numOrigine, int numDestination, int cout) throw(std::bad_alloc, std::logic_error)
*
* \param[in]	numOrigine		Numéro de la station d'origine de l'arc.
* \param[in]	numDestination	Numéro de la station de destination de l'arc.
* \param[in]	cout			Distance entre les deux stations de l'arc.
*/
void Graphe::ajouterArc(int numOrigine, int numDestination, int cout) throw(std::bad_alloc, std::logic_error)
{
	Sommet* destination = this->_getSommet(numDestination);
	Sommet* origine = this->_getSommet(numOrigine);
	if (destination != 0 && origine != 0)
	{
		if(arcExiste(numOrigine, numDestination)){
			throw std::logic_error ("Ajout arc: Il y a déjà un arc orienté entre ces deux sommets!");
		}
		Arc* nouveau = new Arc(destination,cout);
		nouveau->suivDest = origine->listeDest; // Ajuste le pointeur suivant du nouvel élément au premier de la liste
		origine->listeDest = nouveau; // Change le pointeur vers le nouvel élément
	}else
	{
		throw std::logic_error ("Ajout arc: Un des deux sommets n'existent pas!");
	}
	/*if (sommetExiste(numOrigine) && (sommetExiste(numDestination)))
	{
		if(arcExiste(numOrigine, numDestination)){
			throw std::logic_error ("Ajout arc: Il y a déjà un arc orienté entre ces deux sommets!");
		}
		Sommet* destination = this->_getSommet(numDestination);
		Sommet* courant = this->listSommets;
		while (courant != 0)
		{
			if (courant->numero == numOrigine)
			{
				Arc* nouveau = new Arc(destination,cout);
				nouveau->suivDest = courant->listeDest; // Ajuste le pointeur suivant du nouvel élément au premier de la liste
				courant->listeDest = nouveau; // Change le pointeur vers le nouvel élément
			}
		courant = courant->suivant;
		}
	}
	else
	{
		throw std::logic_error ("Ajout arc: Un des deux sommets n'existent pas!");
	}*/

}

/**
* \brief Enlève un arc du graphe
* \fn void enleverArc(int numOrigine, int numDestination) throw(std::logic_error)
*
* \param[in]	numOrigine		Numéro de la station d'origine de l'arc.
* \param[in]	numDestination	Numéro de la station de destination de l'arc.
*/
void Graphe::enleverArc(int numOrigine, int numDestination) throw(std::logic_error)
{
	if (sommetExiste(numOrigine) && (sommetExiste(numDestination)))
	{
		Sommet* destination = this->_getSommet(numDestination);
		Sommet* courant = this->listSommets;
		while (courant != 0)
		{
			if(courant->numero == numOrigine)
			{
				if (!arcExiste(numOrigine, numDestination))
				{
					throw std::logic_error ("EnleverArc : Il n'y a pas d'arc entre les 2 sommets!");
				}					
				Arc* arcCourant = courant->listeDest;
				Arc* precedent = 0;
				while (arcCourant != 0 && arcCourant->dest != destination)
				{
					precedent = arcCourant;
					arcCourant = arcCourant->suivDest;
				}
				if (arcCourant == courant->listeDest) // début de la liste
				{
					courant->listeDest = courant->listeDest->suivDest;
				}
				else
				{
					precedent->suivDest = arcCourant->suivDest;
				}
				arcCourant->suivDest = 0;
				delete arcCourant;
			}
			courant = courant->suivant;
		}
	}
	else
	{
		throw std::logic_error ("EnleverArc : Un des sommets n'est pas dans le graphe!");
	}
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Données sur le graphe (incluant listes de sommets)
// _________________________________________________________________________________________________

/**
* \brief Retourne le nombre de sommets dans la liste des sommets
* \fn int nombreSommets() const
*
* \return	Le nombre de sommets du graphe.
*/
int Graphe::nombreSommets() const
{
	return this->nbSommets;
}

/**
* \brief Indique si la liste des sommets est vide
* \fn bool estVide() const
*
* \return	Vrai si le graphe est vide, faux sinon.
*/
bool Graphe::estVide() const
{
	if (this->nbSommets == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

/**
* \brief Retourne la liste des numéros des sommets dans un vecteur d'entiers
* \fn std::vector<int> Graphe::listerSommets() const
*
* \return Retourne un vecteur contenant les numéros des sommets du graphe
*/
std::vector<int> Graphe::listerSommets() const
{
	std::vector<int> listeSommets;
	Sommet* courant = this->listSommets;
	while (courant != 0)
	{
		listeSommets.insert(listeSommets.end(), courant->numero);
		courant = courant->suivant;
	}
	return listeSommets;
}

/**
* \brief Retourne la liste des noms des sommets dans un vecteur
* \fn std::vector<std::string> Graphe::listerNomsSommets() const
*
* \return Un vecteur contenant les noms des sommets du graphe
*/
std::vector<std::string> Graphe::listerNomsSommets() const
{
	std::vector<string> listeSommets;
	Sommet* courant = this->listSommets;
	while (courant != 0)
	{
		listeSommets.insert(listeSommets.end(), courant->nom);
		courant = courant->suivant;
	}
	return listeSommets;
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Trouver numéro sommet
// _________________________________________________________________________________________________

/**
* \brief Retourne le numéro d'un sommet selon son nom
* \fn int Graphe::getNumeroSommet(const std::string& nom) const throw (std::logic_error)
*
* \param[in]	nom		Nom de la station
*
* \return Le numéro du sommet
*/
int Graphe::getNumeroSommet(const std::string& nom) const throw (std::logic_error){
	if (this->estVide()){
		throw std::logic_error("Il n'y a pas de sommets dans le graphe");
	}
	Sommet* courant = this->listSommets;
	while (courant != 0){
		if (courant->nom == nom){
			return courant->numero;
		}
	}
	throw std::logic_error("Le sommet n'existe pas");
}

/**
* \brief Retourne le numéro d'un sommet selon ses coordonnées
* \fn int Graphe::getNumeroSommet(int x, int y) const throw (std::logic_error)
*
* \param[in]	x	Coordonnées en x d'un sommet
* \param[in]	y	Coordonnées en y d'un sommet
*
* \return Le numéro du sommet
*/
int Graphe::getNumeroSommet(int x, int y) const throw (std::logic_error){
	Sommet* courant = this->listSommets;
	while (courant != 0){
		if (courant->coord.x == x && courant->coord.y == y){
			return courant->numero;
		}
	}
	throw std::logic_error("Le sommet n'existe pas");
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Données à propos des sommets
// _________________________________________________________________________________________________

/**
* \brief Retourne l'existence d'un sommet
* \fn bool Graphe::sommetExiste(int numero) const
*
* \param[in]	numero	Numéro de la station
*
* \return true si le sommet existe, false sinon
*/
bool Graphe::sommetExiste(int numero) const{
	return this->_getSommet(numero) != 0;
}

/**
* \brief Retourne le nom du sommet dont le numéro est passé en argument
* \fn std::string Graphe::getNomSommet(int numero) const throw(std::logic_error)
*
* \param[in] numero	Numéro de la station
*
* \return Le nom du sommet
*/
std::string Graphe::getNomSommet(int numero) const throw(std::logic_error){
	Sommet* temp = this->_getSommet(numero);
	if (temp == 0){
		throw std::logic_error("Le sommet n'existe pas");
	}
	return temp->nom;
}

/**
* \brief Retourne les coordonnées d'un sommet
* \fn void Graphe::getCoordonnesSommet(int numero, int& x, int& y) const
*
* \param[in]	numero	Numéro de la station
* \param[out]	x		Coordonnées en x du sommet
* \param[out]	y		Coordonnées en y du sommet
*/
void Graphe::getCoordonnesSommet(int numero, int& x, int& y) const{
	if (this->estVide()){
		throw std::logic_error("Il n'y a pas de sommets dans le graphe");
	}
	Sommet* temp = this->_getSommet(numero);
	if (temp == 0){
		throw std::logic_error("Le sommet n'existe pas");
	}
	x = temp->coord.x;
	y = temp->coord.y;
}

/**
* \brief Retourne l'ordre d'entrée d'un sommet
* \fn int Graphe::ordreEntreeSommet(int numero) const throw (std::logic_error)
*
* \param[in]	numero	Numéro de la station
*
* \return Ordre d'entré du sommet
*/
int Graphe::ordreEntreeSommet(int numero) const throw (std::logic_error){
	Sommet* recherche = this->_getSommet(numero);
	if (recherche == 0){
		throw std::logic_error("Le sommet n'existe pas");
	}
	return this->ordreEntreeSommet(recherche);
}

/**
* \brief Retourne l'ordre d'entrée d'un sommet
* \fn int Graphe::ordreEntreeSommet(Sommet* som) const
*
* \param[in]	som	Pointeur sur un sommet
*
* \return Ordre d'entré du sommet
*/
int Graphe::ordreEntreeSommet(Sommet* som) const{
	int ordre = 0;
	Sommet* courant = this->listSommets;
	while(courant != 0){
		Arc* arcCourant = courant->listeDest;
		while (arcCourant != 0){
			if (arcCourant->dest == som){
				ordre++;
			}
			arcCourant = arcCourant->suivDest;
		}
		courant = courant->suivant;
	}
	return ordre;
}

/**
* \brief Retourne la liste des numéros des sommets adjacents au sommet passé en argument dans un vecteur d'entiers
* \fn std::vector<int> listerSommetsAdjacents(int numero) const throw(std::logic_error)
*
* \param[in]	numero		Numéro correspondant au sommet.
*
* \return	La liste des numéros des sommets adjacents au sommet.
*/
std::vector<int> Graphe::listerSommetsAdjacents(int numero) const throw(std::logic_error)
{
	if (!this->sommetExiste(numero))
	{
		throw std::logic_error ("listerSommetsAdjacents : Le sommet n'existe pas!");
	}
	Sommet* courant = this->_getSommet(numero);
	Arc* arcCourant = courant->listeDest;
	std::vector<int> listeSommetsAdj;
	while (arcCourant != 0)
	{
		listeSommetsAdj.insert(listeSommetsAdj.end(), arcCourant->dest->numero);
		arcCourant = arcCourant->suivDest;
	}
	return listeSommetsAdj;
}

/**
* \brief Retourne l'ordre de sortie d'un sommet
* \fn int ordreSortieSommet(int numero) const throw(std::logic_error)
*
* \param[in]	numero		Numéro du sommet.
*
* \return	Ordre de sortie du sommet.
*/
int Graphe::ordreSortieSommet(int numero) const throw(std::logic_error)
{
	if (!this->sommetExiste(numero))
	{
		throw std::logic_error ("ordreSortieSommet : Le sommet n'existe pas!");
	}
	Sommet* courant = this->_getSommet(numero);
	return this->ordreSortieSommet(courant);
}

/**
* \brief Retourne l'ordre de sortie d'un sommet
* \fn int ordreSortieSommet(Sommet* som) const throw(std::logic_error)
*
* \param[in]	som		Le sommet en question.
*
* \return	Ordre de sortie du sommet.
*/
int Graphe::ordreSortieSommet(Sommet* som) const
{
	Arc* arcCourant = som->listeDest;
	int cpt = 0;
	while (arcCourant != 0)
	{
		cpt++;
		arcCourant = arcCourant->suivDest;
	}
	return cpt;
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Données à propos des sommets
// _________________________________________________________________________________________________

/**
* \brief Retourne l'existence d'un arc
* \fn bool arcExiste(int numOrigine, int numDestination) const throw(std::logic_error)
*
* \param[in]	numOrigine		Sommet d'origine de l'arc.
* \param[in]	numDestination	Sommet de destination de l'arc.
*
* \return	Vrai si l'arc entre les sommets existe, faux sinon.
*/
bool Graphe::arcExiste(int numOrigine, int numDestination) const throw(std::logic_error)
{
	Sommet* origine = this->_getSommet(numOrigine);
	Sommet* dest = this->_getSommet(numDestination);
	if (origine == 0 || dest == 0){
		throw std::logic_error("L'un des sommets est inexistant");
	}
	return (this->_getArc(origine,dest) != 0);
}

/**
* \brief Retourne le coût d'un arc passé en argument
* \fn int getCoutArc(int numOrigine, int numDestination) const throw(std::logic_error)
*
* \param[in]	numOrigine		Sommet d'origine de l'arc.
* \param[in]	numDestination	Sommet de destination de l'arc.
*
* \return	Le coût de l'arc entre les deux sommets.
*/
int Graphe::getCoutArc(int numOrigine, int numDestination) const throw(std::logic_error)
{
	Sommet* origine = this->_getSommet(numOrigine);
	Sommet* dest = this->_getSommet(numDestination);
	if (origine == 0 || dest == 0){
		throw std::logic_error("L'un des sommets est inexistant");
	}
	Arc* arc = this->_getArc(origine,dest);
	if (arc == 0){
		throw std::logic_error("L'arc est inexistant");
	}
	return (arc->cout);
}



// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Fonctions plus complexes
// _________________________________________________________________________________________________

/**
* \brief Déterminer la fermeture transitive du graphe.
* \fn Graphe fermetureGraphe() const throw(std::bad_alloc)
*
* \return	La fermeture transitive du graphe.
*/
Graphe Graphe::fermetureGraphe() const throw(std::bad_alloc)
{
	Graphe graphe(*this);
	Sommet* sommet_k = graphe.listSommets;
	while (sommet_k != 0) //Boucle sur les sommets intermÃ©diaires
	{
		Sommet* sommet_i = graphe.listSommets;
		while (sommet_i != 0)  //Boucle sur les sommets de dÃ©part
		{
			Arc* arc_ik = graphe._getArc(sommet_i, sommet_k);
			if (arc_ik != 0){
				Sommet* sommet_j = graphe.listSommets;
				while (sommet_j != 0)  //Boucle sur les sommets adjacents
				{
					Arc* arc_kj = graphe._getArc(sommet_k, sommet_j);
					if (arc_kj != 0){
						Arc* arc_ij = graphe._getArc(sommet_i, sommet_j);
						if (arc_ij != 0)
						{
							arc_ij->cout = min(arc_ij->cout, (arc_ik->cout + arc_kj->cout));
						}
						else
						{
							Arc* nouveau = new Arc(sommet_j, arc_kj->cout + arc_ik->cout);
							nouveau->suivDest = sommet_i->listeDest;
							sommet_i->listeDest = nouveau;
							//graphe.ajouterArc(sommet_i->numero, sommet_j->numero, arc_kj->cout + arc_ik->cout);
						}
					}
					sommet_j = sommet_j->suivant;
				}
			}
			sommet_i = sommet_i->suivant;
		}
		sommet_k = sommet_k->suivant;
	}
	return graphe;
}

/**
* \brief Détermine si le graphe est fortement connexe ou non
* \fn bool estFortementConnexe()const
*
* \return	Vrai si le graphe est fortement connexe, faux sinon.
*/
bool Graphe::estFortementConnexe()const
{
	Sommet* courant = this->listSommets;
	Graphe graphe = fermetureGraphe();
	while (courant != 0)
	{
		int ordre = graphe.ordreSortieSommet(courant->numero);
		if (ordre != this->nbSommets)
		{
			return false;
		}
		courant = courant->suivant;
	}
	return true;
}

/**
* \brief Détermine les composantes fortement connexes et les mémorise dans un conteneur passé en paramètre
* \fn void Graphe::getComposantesFortementConnexes(std::vector< std::vector<std::string> > & composantes)const
*
* \param[out]	composantes	Double vecteur comprenant les différentes composantes fortement connexes
*/
void Graphe::getComposantesFortementConnexes(std::vector< std::vector<std::string> > & composantes)const{
	Graphe fermeture = this->fermetureGraphe();
	Sommet* courant = 0;
	while(fermeture.listSommets != 0){
		courant = fermeture.listSommets;
		std::vector<std::string> compo;
		compo.insert(compo.begin(), courant->nom);
		Arc* arcCourant = courant->listeDest;
		while(arcCourant != 0){
			if (arcCourant->dest != courant){
				Arc* j = arcCourant->dest->listeDest;
				while(j != 0){
					if (j->dest == courant){
						compo.insert(compo.end(), arcCourant->dest->nom);
						fermeture._enleverSommet(arcCourant->dest);
						break;
					}
					j = j->suivDest;
				}
				if (j == 0){
					break;
				}
			}else{
				courant->listeDest = courant->listeDest->suivDest;
				delete arcCourant;
			}
			arcCourant = courant->listeDest;
		}
		fermeture._enleverSommet(courant);
		composantes.insert(composantes.end(), compo);
	}
}

/**
* \brief Trouve le plus court chemin entre deux points en utilisant l'algorithme de Bellman-Ford et le retourne
* \fn int bellmanFord(const std::string & nomOrigine, const std::string & nomDestination, std::vector<std::string> & chemin) throw(std::bad_alloc, std::logic_error)
*
* \param[in]	nomOrigine		Nom du sommet d'origine.
* \param[in]	nomDestination	Nom de sommet de destination.
* \param[in]	chemin			Vecteur contenant un chemin
*
* \return	Chemin le plus court.
*/
int Graphe::bellmanFord(const std::string & nomOrigine, const std::string & nomDestination, std::vector<std::string> & chemin) throw(std::bad_alloc, std::logic_error)
{
	//Initialisation
	Sommet* origine = this->_getSommet(nomOrigine);
	Sommet* destination = this->_getSommet(nomDestination);
	if (origine == 0 || destination == 0)
	{
		throw std::logic_error ("bellmanFord : Le sommet d'origine ou de destination n'existe pas!");
	}
	this->_initPathFinding(nomOrigine,nomDestination,origine,destination);

	//Créer structure
	Noeud* list = this->_creerSousStructure();	
	Noeud* sous_origine = this->_retirerSousStructure(origine, list);
	sous_origine->precedent = 0;
	sous_origine->suivant = list;
	list = sous_origine;
	Noeud* courant = 0;

	//Algo Belman-Ford
	int k = 1;
	int n = this->nbSommets;
	bool stable;
	do
	{
		stable = true;
		while (list != 0) {
		courant = list;
		list = courant->suivant;
		if (list != 0){
			list->precedent = 0;
		}
			Arc* arcCourant = courant->val->listeDest;
			while (arcCourant != 0)
			{
				//Relâchement
				int nouveauCout = courant->val->cout + arcCourant->cout;
				if (nouveauCout < arcCourant->dest->cout)
				{
					arcCourant->dest->predecesseur = courant->val;
					arcCourant->dest->cout = nouveauCout;
					stable = false;
					// Retrier dans la liste
					list = this->_trier(arcCourant->dest, list);
				}
				arcCourant = arcCourant->suivDest;
			}
			courant = courant->suivant;
		}
		k = k++;
	}while (stable == false && k < n+1);

	//Trouver chemin
	this->_recupererChemin(destination, chemin);
	if (destination->cout == std::numeric_limits<int>::max())
	{
		return -1;
	}
	return destination->cout;
}

/**
* \brief Trouve le plus court chemin entre deux points en utilisant l'algorithme de Dijsktra et le retourne
* \fn int Graphe::dijkstra(const std::string& nomOrigine, const std::string& nomDestination, std::vector<std::string> & chemin) throw(std::bad_alloc, std::logic_error)
*
* \param[in]	nomOrigine	Nom de la station d'origine
* \param[in]	nomDestination	Nom de la station de destination
* \param[out]	chemin	Vecteur contenant le chemin trouvé (en ordre)
*
* \return Le cout du chemin le plus court
*/
int Graphe::dijkstra(const std::string& nomOrigine, const std::string& nomDestination, std::vector<std::string> & chemin) throw(std::bad_alloc, std::logic_error){
	Sommet* origine = this->_getSommet(nomOrigine);
	Sommet* destination = this->_getSommet(nomDestination);
	if (origine == 0 || destination == 0){
		throw std::logic_error("L'origine ou la destination n'est pas atteignable");
	}
	this->_initPathFinding(nomOrigine, nomDestination, origine, destination);
	Noeud* list = this->_creerSousStructure();
	if (origine->numero != list->val->numero){
		Noeud* sous_origine = this->_retirerSousStructure(origine, list);
		// Ajout de l'origine au début
		sous_origine->precedent = 0;
		sous_origine->suivant = list;
		list = sous_origine;
	}

	Noeud* courant = 0;
	// Algorithme de Dijkstra
	while(list != 0) {
		courant = list;
		list = courant->suivant;
		if (list != 0){
			list->precedent = 0;
		}
		Arc* arcCourant = courant->val->listeDest;
		while (arcCourant != 0){
			if (arcCourant->dest->etat == false){
				int nouveau_cout = arcCourant->cout + courant->val->cout;
				if (arcCourant->dest->cout > nouveau_cout){
					arcCourant->dest->predecesseur = courant->val;
					arcCourant->dest->cout = nouveau_cout;
					// Retrier dans la liste
					list = this->_trier(arcCourant->dest, list);
				}
			}
			arcCourant = arcCourant->suivDest;
		}
		courant->val->etat = true;
		if (courant->val == destination){
			delete courant;
			break;
		}
		delete courant;
	}
	// Trouver le chemin
	list = this->_deleteSousStructure(list);
	this->_recupererChemin(destination, chemin);
	if (destination->cout == std::numeric_limits<int>::max())
	{
		return -1;
	}
	return destination->cout;
}

/**
* \brief Indique si chemin existe entre deux sommets (Utilise Dijkstra)
* \fn bool Graphe::cheminExiste(Sommet* origine, Sommet* destination) throw(std::bad_alloc, std::logic_error)
*
* \param[in]	origine	Pointeur sur le sommet d'origine
* \param[in]	destination Pointeur sur le sommet de destination
*
* \return true si un chemin existe, false sinon
*/
bool Graphe::cheminExiste(Sommet* origine, Sommet* destination) throw(std::bad_alloc){
	this->_initPathFinding(origine->nom, destination->nom, origine, destination);
	Noeud* list = this->_creerSousStructure();
	if (origine->numero != list->val->numero){
		Noeud* sous_origine = this->_retirerSousStructure(origine, list);
		// Ajout de l'origine au début
		sous_origine->precedent = 0;
		sous_origine->suivant = list;
		list = sous_origine;
	}

	Noeud* courant = 0;
	// Algorithme de Dijkstra
	while(list != 0) {
		courant = list;
		list = courant->suivant;
		if (list != 0){
			list->precedent = 0;
		}
		if(courant->val->cout == std::numeric_limits<int>::max()){
			delete courant;
			break;
		}
		Arc* arcCourant = courant->val->listeDest;
		while (arcCourant != 0){
			if (arcCourant->dest->etat == false){
				int nouveau_cout = arcCourant->cout + courant->val->cout;
				if (arcCourant->dest->cout > nouveau_cout){
					arcCourant->dest->predecesseur = courant->val;
					arcCourant->dest->cout = nouveau_cout;
					// Retrier dans la liste
					list = this->_trier(arcCourant->dest, list);
				}
			}
			arcCourant = arcCourant->suivDest;
		}
		courant->val->etat = true;
		if (courant->val == destination){
			delete courant;
			break;
		}
		delete courant;
	}
	// Trouver le chemin
	list = this->_deleteSousStructure(list);
	if (destination->cout == std::numeric_limits<int>::max())
	{
		return false;
	}
	return true;
}

#include <ctime>

/**
* \brief Trouve les points d'articulation du graphe et les retourne
* \fn void Graphe::getPointsArticulation(std::vector<std::string>& sommets)
*
* \param[out]	sommets	Vecteur contenant la liste des points d'articulation
*/
void Graphe::getPointsArticulation(std::vector<std::string>& sommets){
	Sommet* courant = this->listSommets;
	//Parcours de tout les sommets du graphe
	while (courant != 0){
		Graphe copie = *this;
		Sommet* aEnlever = copie._getSommet(courant->numero);

		Noeud* listDepart = copie._predecesseurs(aEnlever);
		Noeud* listArrivee = copie._successeurs(aEnlever);
		
		copie._enleverSommet(aEnlever);

		Noeud* j = listDepart;
		bool done = false;
		while (j != 0 && !done){
			Noeud* k = listArrivee;
			while (k != 0){
				std::vector<std::string> v;
				if (k->val->nom != j->val->nom){
					if (!copie.cheminExiste(j->val, k->val)){
						sommets.insert(sommets.end(), courant->nom);
						done = true;
						break;
					}
				}
				k = k->suivant;
			}
			j = j->suivant;
		}

		this->_deleteSousStructure(listArrivee);
		this->_deleteSousStructure(listDepart);
		courant = courant->suivant;
	}
}

/**
* \brief Trouve le plus court chemin entre deux points en utilisant l'algorithme de A Star (A*) et le retourne
* \fn int aStar(const std::string & nomOrigine, const std::string & nomDestination, std::vector<std::string> & chemin) throw(std::bad_alloc, std::logic_error)
*
* \param[in]	nomOrigine		Nom du sommet d'origine.
* \param[in]	nomDestination	Nom de sommet de destination.
* \param[in]	chemin			Vecteur du chemin.
*
* \return	Distance du chemin.
*/
int Graphe::aStar(const std::string& nomOrigine, const std::string& nomDestination, std::vector<std::string>& chemin) throw (std::bad_alloc, std::logic_error){
	Sommet* origine = this->_getSommet(nomOrigine);
	Sommet* destination = this->_getSommet(nomDestination);
	if (origine == 0 || destination == 0){
		throw std::logic_error("Le sommet d'origine ou de destination n'existe pas");
	}
	this->_initPathFinding(nomOrigine, nomDestination, origine, destination);

	Noeud* list = new Noeud(origine);
	list->suivant = 0;
	list->precedent = 0;

	while (list != 0){
		// Prendre le premier élément de la liste
		Noeud* n = list;
		if (n->suivant != 0){
			n->suivant->precedent = 0;
		}
		list = list->suivant;
		Sommet* courant = n->val;
		delete n;
		//Marqué le sommet
		courant->etat = true;
		if(courant == destination){
			break;
		}
		//Parcourir les arcs
		Arc* arcCourant = courant->listeDest;
		while (arcCourant != 0){
			if (arcCourant->dest->etat == false){
				if (arcCourant->dest->cout == std::numeric_limits<int>::max()){
					arcCourant->dest->cout = arcCourant->cout + courant->cout;
					arcCourant->dest->predecesseur = courant;
					arcCourant->dest->coutHeuristique = this->_distanceEuclidienne(courant->coord, arcCourant->dest->coord);//CALCULER DISTANCE
					//Ajouter à list
					Noeud* nouveau = new Noeud(arcCourant->dest);
					nouveau->precedent = 0;
					nouveau->suivant = list;
					if (list != 0){
						list->precedent = nouveau;
					}
					list =  nouveau;
					list = this->_trier(nouveau->val, list);
				}else{
					int nouveau_cout = arcCourant->cout + courant->cout + arcCourant->dest->coutHeuristique;
					if (nouveau_cout < arcCourant->dest->coutTotal()){
						arcCourant->dest->cout = arcCourant->cout + courant->cout;
						arcCourant->dest->predecesseur = courant;
						list = this->_trier(arcCourant->dest, list);
					}
				}
			}
			arcCourant = arcCourant->suivDest;
		}
	}

	list = this->_deleteSousStructure(list);
	this->_recupererChemin(destination, chemin);
	if (destination->cout == std::numeric_limits<int>::max())
	{
		return -1;
	}
	return destination->cout;
}

/**
* \brief Trouve le plus long chemin entre deux points en utilisant l'algorithme de A Star (A*) et le retourne
* \fn int Graphe::aStarInverse(const std::string& nomOrigine, const std::string& nomDestination, std::vector<std::string>& chemin) throw (std::bad_alloc, std::logic_error)
*
* \param[in]	nomOrigine		Nom du sommet d'origine.
* \param[in]	nomDestination	Nom de sommet de destination.
* \param[in]	chemin			Vecteur du chemin.
*
* \return Le cout du chemin le plus long
*/
int Graphe::aStarInverse(const std::string& nomOrigine, const std::string& nomDestination, std::vector<std::string>& chemin) throw (std::bad_alloc, std::logic_error){
	Sommet* origine = this->_getSommet(nomOrigine);
	Sommet* destination = this->_getSommet(nomDestination);
	if (origine == 0 || destination == 0){
		throw std::logic_error("Le sommet d'origine ou de destination n'existe pas");
	}
	this->_initPathFinding(nomOrigine, nomDestination, origine, destination);

	Noeud* list = new Noeud(origine);
	list->suivant = 0;
	list->precedent = 0;

	while (list != 0){
		// Prendre le premier élément de la liste
		Noeud* n = list;
		if (n->suivant != 0){
			n->suivant->precedent = 0;
		}
		list = list->suivant;
		Sommet* courant = n->val;
		delete n;

		//Marqué le sommet
		courant->etat = true;
		if(courant == destination){
			break;
		}

		//Parcourir les arcs
		Arc* arcCourant = courant->listeDest;
		while (arcCourant != 0){
			if (arcCourant->dest->etat == false){
				if (arcCourant->dest->cout == std::numeric_limits<int>::max()){
					arcCourant->dest->cout = arcCourant->cout + courant->cout;
					arcCourant->dest->predecesseur = courant;
					arcCourant->dest->coutHeuristique = this->_distanceEuclidienne(courant->coord, arcCourant->dest->coord);//CALCULER DISTANCE
					//Ajouter à list
					Noeud* nouveau = new Noeud(arcCourant->dest);
					nouveau->precedent = 0;
					nouveau->suivant = list;
					if (list != 0){
						list->precedent = nouveau;
					}
					list =  nouveau;
					list = this->_trierInverse(nouveau->val, list);
				}else{
					int nouveau_cout = arcCourant->cout + courant->cout + arcCourant->dest->coutHeuristique;
					if (nouveau_cout > arcCourant->dest->coutTotal()){
						arcCourant->dest->cout = arcCourant->cout + courant->cout;
						arcCourant->dest->predecesseur = courant;
						list = this->_trierInverse(arcCourant->dest, list);
					}
				}
			}
			arcCourant = arcCourant->suivDest;
		}
	}

	list = this->_deleteSousStructure(list);
	this->_recupererChemin(destination, chemin);
	if (destination->cout == std::numeric_limits<int>::max())
	{
		return -1;
	}
	return destination->cout;
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Méthodes auxiliaires (getters)
// _________________________________________________________________________________________________

/**
* \brief Trouve l'adresse d'un sommet à partir de son numéro
* \fn Graphe::Sommet* Graphe::_getSommet(int numero) const
*
* \param[in]	numero Numéro du sommet recherché
*
* \return Pointeur sur le sommet trouvé
*/
Graphe::Sommet* Graphe::_getSommet(int numero) const{
	Sommet* courant = this->listSommets;
	while (courant != 0){
		if (courant->numero == numero){
			return courant;
		}
		courant = courant->suivant;
	}
	return 0;
}

/**
* \brief Trouve l'adresse d'un sommet à partir de son nom
* \fn Graphe::Sommet* Graphe::_getSommet(std::string nom) const
*
* \param[in]	nom	Nom du sommet recherché
*
* \return Pointeur sur le sommet trouvé
*/
Graphe::Sommet* Graphe::_getSommet(std::string nom) const{
	Sommet* courant = this->listSommets;
	while (courant != 0){
		if (courant->nom == nom){
			return courant;
		}
		courant = courant->suivant;
	}
	return 0;
}

/**
* \brief Trouve l'adresse d'un arc entre deux sommets
* \fn Arc * _getArc(Sommet * sommet1, Sommet * sommet2) const
*
* \param[in]	sommet1		Sommet d'origine.
* \param[in]	sommet2		Sommet de destination.
* \return	L'arc entre les deux sommets est retournée, 0 si aucun arc n'a été trouvé
*/
Graphe::Arc * Graphe::_getArc(Sommet * sommet1, Sommet * sommet2) const
{
	Arc* arcCourant = sommet1->listeDest;
	while (arcCourant != 0)
	{
		if (arcCourant->dest == sommet2)
		{
			return arcCourant;
		}
		arcCourant = arcCourant->suivDest;
	}
	 return 0;
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Méthodes auxiliaires (destruction + copie)
// _________________________________________________________________________________________________

/**
* \brief Destruction du graphe
* \fn void Graphe::_detruireGraphe()
*
*/
void Graphe::_detruireGraphe(){
	Sommet* courant = this->listSommets;
	while (courant != 0){
		//Arc* arcCourant = courant->listeDest;
		while(courant->listeDest != 0){
			Arc* arcCourant = courant->listeDest;
			courant->listeDest = courant->listeDest->suivDest;
			delete arcCourant;
		}
		courant = courant->suivant;
	}
	while (this->listSommets != 0){
		courant = this->listSommets;
		this->listSommets = this->listSommets->suivant;
		delete courant;
	}
}

/**
* \brief Copie d'un graphe
* \fn _copierGraphe(const Graphe &source) throw(std::bad_alloc)
*
* \param[in]	source		Le graphe source a copier.
*
*/
void Graphe::_copierGraphe(const Graphe &source) throw(std::bad_alloc)
{
	 this->_detruireGraphe();
	 Sommet* courant = source.listSommets;
     while (courant != 0)
	 {	
		 this->ajouterSommet(courant->numero,courant->nom,courant->coord.x,courant->coord.y);
		 courant = courant ->suivant;
	 }
	 courant = source.listSommets;
     while (courant != 0)
	 {	
		 Arc* arcCourant = courant->listeDest;
		 while (arcCourant != 0)
		 {
			 this->ajouterArc(courant->numero, arcCourant->dest->numero,arcCourant->cout);
			 arcCourant = arcCourant->suivDest;
		 }
		 courant = courant ->suivant;
	 }
}

/**
* \brief Enlever un sommet à partir de son adresse
* \fn void Graphe::_enleverSommet(Sommet * sommetAEnlever)
*
* \param[in]	sommetAEnlever	Pointeur sur le sommet à retirer
*/
void Graphe::_enleverSommet(Sommet * sommetAEnlever){
	// Retirer toute les arcs vers ce sommet
	Sommet* courant = this->listSommets;
	while (courant != 0){
		Arc* arcCourant = courant->listeDest;
		Arc* precedent  = 0;
		while (arcCourant != 0){
			if (arcCourant->dest == sommetAEnlever){
				if (precedent != 0){
					precedent->suivDest = arcCourant->suivDest;
				}else{
					courant->listeDest = arcCourant->suivDest;
				}
				Arc* temp = arcCourant;
				arcCourant = arcCourant->suivDest;
				delete temp;
			}else{
				precedent = arcCourant;
				arcCourant = arcCourant->suivDest;
			}
		}
		courant = courant->suivant;
	}
	// Retirer ce sommet
	if (sommetAEnlever->precedent != 0){
		sommetAEnlever->precedent->suivant = sommetAEnlever->suivant;
	}else{
		this->listSommets = sommetAEnlever->suivant;
	}
	if (sommetAEnlever->suivant != 0){
		sommetAEnlever->suivant->precedent = sommetAEnlever->precedent;
	}
	this->nbSommets--;
	delete sommetAEnlever;
}


// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Méthode concernant la sous-structure des noeauds
// _________________________________________________________________________________________________

/**
* \brief Créer une sous-structure (liste bidirectionnel) contenant toute les sommets du graphe
* \fn Graphe::Noeud* Graphe::_creerSousStructure()
*
* \return Pointeur sur le premier Noeud de la structure
*/
Graphe::Noeud* Graphe::_creerSousStructure(){
	Noeud* begin = 0;
	Sommet* courant = this->listSommets;
	if (courant != 0){
		begin = new Noeud(courant);
		begin->precedent = 0;
		begin->suivant = 0;
		courant = courant->suivant;
	}
	Noeud* precedent = begin;
	while (courant != 0){
		Noeud* nouveau = new Noeud(courant);
		nouveau->suivant = 0;
		nouveau->precedent = precedent;
		precedent->suivant = nouveau;
		precedent = nouveau;
		courant = courant->suivant;
	}
	return begin;
}

/**
* \brief Permet de retirer un Sommet de la sous-structure.
* \fn Graphe::Noeud* Graphe::_retirerSousStructure(Sommet* val, Noeud* structure)
*
* \param[in]	val	Pointeur sur le sommet à retirer dans la structure
* \param[in]	structure	La structure dans lequel retirer le sommet
*
* \return Pointeur sur le Noeud retirer de la structure
*/
Graphe::Noeud* Graphe::_retirerSousStructure(Sommet* val, Noeud* structure){
	Noeud* courant = structure;
	while(courant != 0){
		if (courant->val == val){
			if (courant->precedent != 0){
				courant->precedent->suivant = courant->suivant;
			}
			if (courant->suivant != 0){
				courant->suivant->precedent = courant->precedent;
			}
			return courant;
		}
		courant = courant->suivant;
	}
	return 0;
}

/**
* \brief Replace un élément dans l'ordre croissant dans une sous-structure.
* \fn Graphe::Noeud* Graphe::_trier(Sommet* val, Noeud* structure)
*
* \param[in]	val	Pointeur sur le sommet à replacer
* \param[in]	structure	La structure dans lequel trier l'élément
*
* \return Pointeur sur le premier Noeud de la structure
*/
Graphe::Noeud* Graphe::_trier(Sommet* val, Noeud* structure){
	if (structure != 0){
		Noeud* courant = structure;
		while(courant != 0){
			if (courant->val == val){
				break;
			}
			courant = courant->suivant;
		}
		Noeud* recherche = courant;
		while(recherche->precedent != 0 && recherche->precedent->val->cout > courant->val->cout){
			recherche = recherche->precedent;
		}
		if (recherche != courant){
			if (courant->precedent != 0){
				courant->precedent->suivant = courant->suivant;
			}
			if (courant->suivant != 0){
				courant->suivant->precedent = courant->precedent;
			}
			courant->suivant = recherche;
			courant->precedent = recherche->precedent;
			if (recherche->precedent != 0){
				recherche->precedent->suivant = courant;
			}else{
				structure = courant;
			}
			recherche->precedent = courant;
		}
	}
	return structure;
}

/**
* \brief Replace un élément dans l'ordre DÉCROISSANT dans une sous-structure.
* \fn Graphe::Noeud* Graphe::_trierInverse(Sommet* val, Noeud* structure)
*
* \param[in]	val	Pointeur sur le sommet à replacer
* \param[in]	structure	La structure dans lequel trier l'élément
*
* \return Pointeur sur le premier Noeud de la structure
*/
Graphe::Noeud* Graphe::_trierInverse(Sommet* val, Noeud* structure){
	Noeud* courant = structure;
	while(courant != 0){
		if (courant->val == val){
			break;
		}
		courant = courant->suivant;
	}
	Noeud* recherche = courant;
	while(recherche->suivant != 0 && recherche->suivant->val->coutTotal() > courant->val->coutTotal()){
		recherche = recherche->suivant;
	}
	if (recherche != courant){
		if (courant->precedent != 0){
			courant->precedent->suivant = courant->suivant;
		}else{
			structure = courant->suivant;
		}
		if (courant->suivant != 0){
			courant->suivant->precedent = courant->precedent;
		}
		courant->precedent = recherche;
		courant->suivant = recherche->suivant;
		if (recherche->suivant != 0){
			recherche->suivant->precedent = courant;
		}
		recherche->suivant = courant;
	}
	return structure;
}

/**
* \brief Permet de supprimer toute la mémoire utilisé par une sous-structure.
* \fn Graphe::Noeud* Graphe::_deleteSousStructure(Noeud* begin)
*
* \param[in]	begin	Le début de la structure à libérer
*
* \return Toujours null(0)
*/
Graphe::Noeud* Graphe::_deleteSousStructure(Noeud* begin){
	while(begin != 0){
		Noeud* temp = begin;
		begin = begin->suivant;
		delete temp;
	}
	return 0;
}

/**
* \brief Retourne tout les Noeuds représentant les prédecesseurs d'un sommet
* \fn Graphe::Noeud* Graphe::_predecesseurs(Sommet* val)
*
* \param[in]	val	Pointeur sur le sommet
*
* \return Pointeur sur le premier Noeud de la structure
*/
Graphe::Noeud* Graphe::_predecesseurs(Sommet* val){
	Noeud* listDepart = 0;
	Sommet* i = this->listSommets;
	while (i != 0){
		Arc* arcCourant = i->listeDest;
		while (arcCourant != 0){
			if (arcCourant->dest == val){
				Noeud* nouveau = new Noeud(i);
				nouveau->suivant = listDepart;
				nouveau->precedent = 0;
				if (listDepart != 0){
					listDepart->precedent = nouveau;
				}
				listDepart = nouveau;
				break;
			}
			arcCourant = arcCourant->suivDest;
		}
		i = i->suivant;
	}
	return listDepart;
}

/**
* \brief Retourne tout les Noeuds représentant les successeurs d'un sommet
* \fn Graphe::Noeud* Graphe::_successeurs(Sommet* val)
*
* \param[in]	val	Pointeur sur le sommet
*
* \return Pointeur sur le premier Noeud de la structure
*/
Graphe::Noeud* Graphe::_successeurs(Sommet* val){
	Noeud* listArrivee = 0;
	Arc* arcCourant = val->listeDest;
	while (arcCourant != 0){
		Noeud* nouveau = new Noeud(arcCourant->dest);
		nouveau->suivant = listArrivee;
		nouveau->precedent = 0;
		if (listArrivee != 0){
			listArrivee->precedent = nouveau;
		}
		listArrivee = nouveau;
		arcCourant = arcCourant->suivDest;
	}
	return listArrivee;
}

/**
* \brief Calcul la distance Euclidienne entre deux Coordonnees
* \fn int Graphe::_distanceEuclidienne(Coordonnees source, Coordonnees destination)
*
* \param[in]	source	Coordonnées de la source
* \param[in]	destination	Coordonnées de la destination
*
* \return La distance Euclidienne entre deux Coordonnees
*/
int Graphe::_distanceEuclidienne(Coordonnees source, Coordonnees destination){
	int distance_x = abs(source.x - destination.x);
	int distance_y = abs(source.y - destination.y);
	return sqrt(std::powl(distance_x,2) + std::powl(distance_y,2));
}

// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
//	Méthodes auxiliaires (path finding)
// _________________________________________________________________________________________________

/**
* \brief Récupère le chemin à partir d'un vector dans les données sont inversées
* \fn void Graphe::_recupererChemin(Sommet * destination, std::vector<std::string> & chemin)
*
* \param[in]	destination	Le sommet de destination pour lequel trouver le chemin
* \param[out]	chemin	Vecteur contenant le chemin de l'origine vers la destination
*/
void Graphe::_recupererChemin(Sommet * destination, std::vector<std::string> & chemin){
	Sommet* courant = destination;
	while (courant != 0){
		chemin.insert(chemin.begin(), courant->nom);
		courant = courant->predecesseur;
	}
}

/**
* \brief Initialise les sommets du graphe dans le but d'utiliser des méthodes pour trouver des chemins
* \fn void _initPathFinding(const std::string & nomOrigine, const std::string & nomDestination, Sommet * & origine, Sommet * &destination) throw(std::logic_error)
*
* \param[in]	nomOrigine		Nom du sommet d'origine.
* \param[in]	nomDestination  Nom du sommet de destination.
* \param[in]	origine		Sommet d'origine.
* \param[in]	destination  Sommet de destination.
*/
void Graphe::_initPathFinding(const std::string & nomOrigine, const std::string & nomDestination, Sommet * & origine, Sommet * &destination) throw(std::logic_error)
{
       Sommet* courant = this->listSommets;
       if (origine == 0 || destination == 0)
       {
             throw logic_error("initPathFinding : Le sommet d'origine ou de destination n'existe pas!");
       }
       while (courant != 0)
       {
             courant->etat = false;
             courant->predecesseur = 0;
             courant->cout = std::numeric_limits<int>::max();
             courant->coutHeuristique = std::numeric_limits<int>::max();
             courant = courant->suivant;
       }
       origine->etat = true;
       origine->predecesseur = 0;
       origine->cout = 0;
       origine->coutHeuristique = std::numeric_limits<int>::max();
}

 